class LRUCache {

    class Node {
        public int key;
        public int val;

        public Node next;
        public Node perv;

        public Node(int key,int val) {
            this.key = key;
            this.val = val;
        }
    }

    public int n;
    public Node head;
    public Node tail;
    public Map<Integer,Node> map;

    public LRUCache(int capacity) {
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.perv = head;
        map = new HashMap<>();
        n = capacity;
    }

    public int get(int key) {
        if(map.containsKey(key))  {
            Node node = map.get(key);
            refresh(node);
            return node.val;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = null;
        if(map.containsKey(key)) {
            //覆盖
            node = map.get(key);
            node.val = value;
        } else {
            if(map.size() == n) {
                Node del = head.next;
                map.remove(del.key);
                delete(del);
            }
            //放入map
            node = new Node(key,value);
            map.put(key,node);
        }
        refresh(node);
    }

    public void refresh(Node node) {
        delete(node);//删除的是指定节点
        node.next = tail;
        tail.perv.next = node;
        node.perv = tail.perv;
        tail.perv = node;

    }

    public void delete(Node node) {
        if(node.perv !=null) {
            node.perv.next = node.next;
            node.next.perv = node.perv;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */